#include <stdio.h>
#include <stdlib.h>

// 计数排序函数
void CountSort(int* a, int n) {
    // 初始化最大值和最小值为数组的第一个元素
    int max = a[0], min = a[0];

    // 遍历数组，找到最大值和最小值
    for (int i = 1; i < n; i++) { // 注意这里从1开始，因为第一个元素已经用于初始化
        if (a[i] > max)
            max = a[i]; // 更新最大值
        if (a[i] < min)
            min = a[i]; // 更新最小值
    }

    // 计算计数数组的大小，并动态分配内存
    int range = max - min + 1;
    int* count = (int*)malloc(range * sizeof(int));
    if (count == NULL) {
        // 内存分配失败处理（这里简单处理为退出程序，实际应用中可能需要更复杂的错误处理）
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    // 初始化计数数组为0
    for (int i = 0; i < range; i++) {
        count[i] = 0;
    }

    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[a[i] - min]++; // 使用元素值减去最小值作为计数数组的下标
    }

    // 计算前缀和，但在这里我们直接通过另一个循环来重建排序后的数组
    // 因此，这一步实际上是和下面的重建步骤合并了

    // 重建排序后的数组
    int* output = (int*)malloc(n * sizeof(int));
    if (output == NULL) {
        // 内存分配失败处理
        free(count); // 释放已经分配的内存
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    int index = 0; // 用于填充输出数组的索引
    for (int i = 0; i < range; i++) {
        // 对于每个在计数数组中出现的元素，将其填充到输出数组中
        while (count[i] > 0) {
            output[index] = i + min;
            index++;
            count[i]--;
        }
    }

    // 将排序后的数组复制回原数组
    for (int i = 0; i < n; i++) {
        a[i] = output[i];
    }

    // 释放动态分配的内存
    free(count);
    free(output);
}

// 主函数，用于测试计数排序
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 调用计数排序函数
    CountSort(arr, n);

    // 打印排序后的数组
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}